2.1 General Principle of Network Coding
It is possible, through a simple observation, to understand what is at stake in network coding applied to meshed networks. Here below, a quick illustration is provided of the gain given by a network coding. A communications network can be modeled by a directed graph with several arcs going from one vertex to another. A vertex without a finishing arc is called a source of the network. An arc represents a communications channel with the capacity of one information unit per time unit, without prejudging the issue of whether several channels can communicate at the same time.
Referring now to FIGS. 1a and 1b, a classic (and pedagogical) example of network coding is presented. A wireless network is formed by nodes A, B and C. A and C are far too distant and have to use B as a communications relay. Without network coding (in the case of FIG. 1a) four successive media would have to be used (because in this example a same physical channel is shared for A, B and C) to communicate from A to C and then from C to A. On the other hand, with simple network coding (the case of FIG. 1b) performed on the relay B using bit-by-bit addition of the information received from A and C, and then transmission of this sum simultaneously to A and C, it can be seen that A and C, with their own information being known, can deduce the information intended for them from the sum received. The medium has to be taken three times in succession. The result of this is a gain in capacity of the network, and a gain in latency.
FIGS. 2a, 2b and 2c illustrate the problem of implementing a network coding, where FIGS. 2a and 2b correspond to a well adapted network coding whereas FIG. 2c corresponds to an incorrectly adapted one. In this example, the transmissions are considered to occur without delay. The network considered, called a butterfly network, comprises two source nodes A and B, two relay nodes C and D, and two destination nodes E and F. FIG. 2a shows that there are two disjointed paths from the source nodes A and B to the destination node E: one path starts from A and goes directly to E, the other goes from A and goes through C and D before reaching E. Node E is thus able to retrieve pieces of information “a” and “b”. FIG. 2b shows that there are two disjointed paths from the source nodes A and B to the destination node F: one starts from B and goes directly to F, the other starts from A and passes through C and D before reaching F. Node F is thus also able to retrieve pieces of information “a” and “b”. FIG. 2c shows that if the link between the nodes A and E no longer has the capacity to pass a piece of information (“a”), the destination node E will receive a piece of encoded information (“a+b”) coming from D which it will never be able to decode.
2.2 The Usable Network Codes
Not all the nodes of a network necessarily take part in a significant coding operation. They may carry out trivial coding, that is they may take incoming data elements and retransmit them. A combining node is the term applied to a node of the network that forms a non-trivial operation on the incoming data.
As we have seen in the above-mentioned examples, a simple code consists of the bit-by-bit addition of data. It follows immediately from this that a linear combination applied to the data coming from the incoming arcs can be used at each encoding node and that a multiplier coefficient can be assigned to each arc going out of the encoding node. At the receiver, if the node knows the various linear combinations used by the “combining” nodes, the decoding is done by applying the inverse matrix formed by the coefficients used in the linear combinations. Naturally, these linear combinations need to be independent.
Furthermore, a node may receive a piece of information which is itself a linear combination of information coming from parent nodes in the hierarchy. The assigning of the nodes must take account of these necessities. Since the data to be transmitted is generally a packet of binary elements or bits having a length q−1, the packets are likened to finite fields with 2q elements. The coefficients of the linear combinations too are chosen in the same finite field.
Koetter and Médard have explained the way to build a network coding scheme (see: “An Algebraic Approach to Network coding” ACM transactions on Networking, Vol 11, No 5, October 2003.). We consider an oriented graph G=(S, E). S is the set of vertices of this graph. E is the set of arcs of this graph, i.e. the set of pairs of S×S which are connected. Let x be the vector representing the data coming from sources at the same point in time. Let z be the vector representing the incoming data entering the receivers at the same point in time. The network is deemed to be without delay, i.e. there is a matrix M such that z=xM. Let F be the matrix of a adjacency associated with the network but modified in the sense that coefficients replace the “1”s that are normally used to mark the presence of an arc. We then define a matrix A and a matrix B which take account of the coefficients on the arcs entering the network portion considered and the coefficients on the outgoing arcs. The transfer matrix M of the system associated with the network is M=A(I−F)−1BT, where I is the identity matrix of the dimension cardinal (E) x cardinal (E). The coefficients (matrices A and B) are chosen in a large-sized finite field so that the determinant of the matrix M is not zero.
Koetter and Médard have also proposed a method in the US patent application 2005/015391 in which the coefficients of the matrix are drawn randomly and then transmitted through the entire network to be made known to all the nodes of the network. This method can be applied to networks of unknown topology. The chances of success depend on the cardinal number of the finite field in which the coefficients are chosen randomly.
2.3 Possibility of Network Coding
The US patent application 2005/0010675 proposes a method to build a network coding scheme that applies the prior art described here above to error-free networks with a single source seeking to transmit the same information to several destinations. It produces a solution for the case of an acyclic network with zero delay. It is based on the work of Ahlswede and uses the Ford Fulkerson algorithm (cf “Maximum Flow through a Network” Canadian Journal of Mathematics, 8, pp 399-404, 1956) to create sub-graphs.
Prior work by Ahlswede and al. in 2000 (see article: R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung “Network Information Flow” I.E.E.E. Transactions on Information Theory Vol 46, No 4, pp 1204-1216, July 2000) already contained a major theorem of existence: “let S be the set of sources of a network; let R be the set of receivers of this network; let G be the graph associated with this network; in G there are h disjointed paths (i.e. paths that do not have an arc in common) (Si,Rj) for 1≦i≦h, for a given receiver Rj, with 1≦j≦card(R); then if the number of sources is equal to h (multicasting capacity of the network), there is a multicasting with a throughput h because of the network coding (being assumed that a link has a capacity of one)”. The problem therefore lies in testing the graph that represents the network to establish the number of disjointed paths.
Ford and Fulkerson's operational search algorithm is well known for resolving problems of transport, especially to determine the maximum flow between a source and a sink. It is also well known in the prior art that this algorithm can be used to obtain the number of disjointed paths (see Appendix).
The US patent application US2005/0010675 mentioned here above, which is a known solution pertaining to network coding uses this algorithm. However, this known solution has several drawbacks.
One drawback of this known solution is that, even if its authors assert that it can be easily extended, the algorithms presented do not take account of the case of a shared medium which obviously entails the existence of delays. It is easy to prove that their method fails for a shared medium, especially in the computation of multicast capacity.
Another drawback of this known solution is that it does not account of the existence of multiple multicast sources.
Furthermore, and more generally, no known technique of network coding is proposed when the number of sources is strictly greater than h (multicast capacity of the network), i.e. when the condition of the above-mentioned theorem is not respected.